package jjn.round1;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Objects;

/**
 * @author Jjn
 * @since 2022/10/4 22:58
 */
public class LeetCode921_MinAddToMakeValid {

    public int minAddToMakeValid(String s) {
        Deque<Character> queue = new LinkedList<>();
        for (Character character : s.toCharArray()) {
            if (Objects.equals(queue.peekLast(), '(') && Objects.equals(character, ')')) {
                queue.pollLast();
            } else {
                queue.offer(character);
            }
        }
        return queue.size();
    }
}
